#include <stdio.h>
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <map>
using namespace std;




//查找数组中出现次数超过size>>1,和出现次数超过size>>2

void Find(const vector<int> &numbers,int & out2, int &out4)
{
  map<int,int> m;
  int i = 0;
  int length = numbers.size();
  for(i = 0;i< length;i++)
  {
    if(m.find(numbers[i]) == m.end())
    {//说明没有找到
     m.insert(make_pair(numbers[i],1)); 
    }
    else
    {
      m[numbers[i]] +=1;
    }
  }

  //循环遍历完成后，就将map设置好了
  
  map<int , int>::iterator it = m.begin();
  while(it != m.end())
  {
    if(it->second > length/2)
    {
      out2 = it->first;
    }
    else
    {
      if(it->second > length/4)
      {
        out4 = it->first;
      }

    }
    it++;

  }
  return;
}


int main()
{

  vector<int> numbers;
  numbers.push_back(4);
  numbers.push_back(4);
  numbers.push_back(-4);
  numbers.push_back(-4);
  numbers.push_back(-4);
  numbers.push_back(4);
  numbers.push_back(89);
  numbers.push_back(4);
  numbers.push_back(4);
  numbers.push_back(4);

  int out2 = -1,out4 = -1;
  Find(numbers, out2, out4);
  if(out2 == -1)
  {
    printf("没有出现次数超过size>>1位的数字\n");
  }
  else
  {
    printf("出现次数超过size>>1:%d\n",out2);
  }
  if(out4 == -1)
  {
    printf("没有出现次数超过size>>2位的数字\n");
  }
  else
  {
    printf("出现次数超过size>>2:%d\n",out4);
  }
  
}
